// Copyright (C) 2011 - Tencent Inc.
// Author: Liu Shaohui (struggleliu@tencent.com)
//
// Created: 09/12/2011 18:10:25
// Description: Dancing link solved the exact cover problem
//

#include "dancing_links/dancing_links.h"


void DancingLinks::PreChooseCol(int col_id) {

}

bool DancingLinks::Search() {
    InitMatrix();
    return DFSSearch(0);
}

void DancingLinks::InitNode(int row, int col) {
    DLNode* node = m_node_map[row * m_col_num + col];
    node->row_id = row;
    node->header = &m_header[col];
    node->up = NULL;
    for(int up_row = row - 1; up_row >= 0; up_row --)
        if (m_matrix[up_row][col]){
            node->up = m_node_map[up_row * m_col_num + col];
            break;
        }
    if (node->up == NULL) {
        node->up = &m_header[col];
        m_header[col].down = node;
    }
    node->down = NULL;
    for(int down_row = row + 1; down_row < m_row_num; down_row ++)
        if (m_matrix[down_row][col]){
            node->down = m_node_map[down_row * m_col_num + col];
            break;
        }
    if (node->down == NULL) {
        node->down = &m_header[col];
        m_header[col].up = node;
    }
    node->left = node;
    for(int left_col = LeftCol(col); left_col != col; left_col = LeftCol(left_col))
        if (m_matrix[row][left_col]) {
            node->left = m_node_map[row * m_col_num + left_col];
            break;
        }
    node->right = node;
    for (int right_col = RightCol(col); right_col != col; right_col = RightCol(col))
        if (m_matrix[row][right_col]) {
            node->right = m_node_map[row * m_col_num + right_col];
            break;
        }
}

void DancingLinks::InitMatrix() {
    m_root = new DLNode();
    m_header = new DLNode[m_col_num];

    m_root->left = &m_header[m_col_num - 1];
    m_header[m_col_num - 1].right = m_root;
    m_root->right = &m_header[0];
    m_header[0].left = m_root;

    for(int col = 0; col + 1 < m_col_num; col ++) {
        m_header[col].right = &m_header[col + 1];
        m_header[col + 1].left = &m_header[col];
    }
    for (int row = 0; row < m_row_num; row ++) {
        for (int col = 0; col < m_col_num; col ++ ) {
            if (m_matrix[row][col]) {
                m_node_map.insert(std::make_pair(row * m_col_num + col, new DLNode()));
            }
        }
    }
    for (int row = 0; row < m_row_num; row ++) {
        for (int col = 0; col < m_col_num; col ++ ) {
            if (m_matrix[row][col]) {
                InitNode(row, col);
            }
        }
    }
}

bool DancingLinks::DFSSearch(int depth) {
    if (m_root->left == m_root) {
        return true;
    }
    DLNode* col = ChooseCol();
    CoverCol(col);
    for (DLNode* row = col->down; row != col; row = row->down) {
        // add a row
        m_choose_cols.push_back(row->row_id);
        for (DLNode* node = row->right; node!= row; node = node->right) {
            CoverCol(node->header);
        }
        DFSSearch(depth + 1);
        for (DLNode* node = row->left; node != row; node = node->left) {
            UnCoverCol(node->header);
        }
        m_choose_cols.pop_back();
    }
    UnCoverCol(col);
    return false;
}

void DancingLinks::CoverCol(DLNode* node) {
    CoverH(node);
    for (DLNode* row = node->down; row != node; row = row->down) {
        for (DLNode* col = row->right; col != row; col = col->right) {
            CoverV(col);
        }
    }
}

void DancingLinks::UnCoverCol(DLNode* node) {
    for (DLNode* row = node->up; row != node; row = row->up) {
        for (DLNode* col = row->left; col != row; col = col->left) {
            UnCoverV(col);
        }
    }
    UnCoverV(node);
}

void DancingLinks::CoverH(DLNode* node) {
    node->left->right = node->right;
    node->right->left = node->left;
}

void DancingLinks::UnCoverH(DLNode* node) {
    node->left->right = node;
    node->right->left = node;
}

void DancingLinks::CoverV(DLNode* node) {
    node->up->down = node->down;
    node->down->up = node->up;
}

void DancingLinks::UnCoverV(DLNode* node) {
    node->up->down = node;
    node->down->up = node;
}

DancingLinks::DLNode* DancingLinks::ChooseCol() {
    return m_root->left;
}

